|
In computer science, cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function ''ƒ'' that maps a finite set ''S'' to itself, and any initial value ''x''0 in ''S'', the sequence of iterated function values : must eventually use the same value twice: there must be some ''i'' ≠ ''j'' such that ''xi'' = ''xj''. Once this happens, the sequence must continue periodically, by repeating the same sequence of values from ''xi'' to ''xj''−1. Cycle detection is the problem of finding ''i'' and ''j'', given ''ƒ'' and ''x''0. ==Example== The figure shows a function ƒ that maps the set ''S'' = to itself. If one starts from ''x''0 = 2 and repeatedly applies ƒ, one sees the sequence of values :2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, .... The cycle in this value sequence is 6, 3, 1. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「cycle detection」の詳細全文を読む スポンサード リンク
|